小牛牛超市选品

题目内容

牛牛在超市采购商品，每件商品有对应价格（均为正整数）。给定预算 $limit$，要求选出连续一段商品，满足两条约束：

• 这段商品总价格严格大于 $limit$
• 这段商品中最贵商品价格 $\le limit$

请找出满足以上两条规则的最短连续商品长度；不存在合法区间输出 $0$。

约束条件：

• $0 < limit < 100$
• $0 < n \le 10$
• $0 < A_i \le 10$

输入描述

• 参数 1：商品数量 $n$
• 参数 2：预算上限 $limit$
• 参数 3：商品价格数组，数组元素代表每件商品价格 $A_i$

输出描述

合法最短区间长度；无合法区间输出 $0$。

样例

样例 1

输入

6 7
2 3 1 2 4 3

输出

3

说明：

• $[4,3]$ 的和为 $7$，不满足严格大于 $7$，作废
• $[2,4,3]$ 的和为 $9>7$，最大值 $4 \le 7$，长度 $3$
• $[3,1,2,4]$ 的和为 $10>7$，长度 $4$

最短合法长度为 $3$。

样例 2

输入

3 11
1 2 3

输出

0

说明： 不满足 $limit$ 约束。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', (input) => {
    const limit = Number(input.split(' ')[1]);
    rl.on('line', (input) => {
        const arr = input.split(' ').map(v => parseInt(v));
        let left = 0;
        let right = 0;
        let min = Infinity;
        function isYes(l, r) {
            let res = 0;
            for(let i=l; i<=r; i++) {
                if (arr[i] > limit) {
                    return false;
                } else {
                    res += arr[i];
                }
            }
            if (res > limit) {
                return true;
            } else {
                return false;
            }
        }
        while(left <= right && right < arr.length) {
            if (isYes(left, right)) {
                min = Math.min(min, right-left+1);
                // console.log(min, left, right);
                left++;
            } else {
                right++;
            }
        }
        console.log(min === Infinity ? 0 : min);
    })
})